The present invention relates to the efficient construction and access of address tables within network mutliplexers and, in particular, to a method and system for efficiently adding addresses to an address table of limited size until the address table is nearly full and for efficiently locating entries within the address table.
Bridges, switches, and routers are networking devices that interconnect two or more distinct physical communication network media, such as ethernets, token rings, and optical fibre media. Network multiplexers forward communications packets received from a first network medium via a first network multiplexer port to one or more destination communications network media via one or more destination network multiplexer ports. In forwarding a communications packet, the network multiplexer accesses an address table that contains a set of associations between network addresses and network multiplexer ports. The network multiplexer compiles the address table over time, monitoring incoming communications packets for newly recognized source addresses that do not yet exist in the address table. Those newly recognized addresses are entered into the address table in association with an indication of the port through which the communications packet was received. Subsequently, when a communications packet is received with a destination address matching an address already entered into the address table, the network multiplexer can determine to which port to forward the communications packet.
The memory resources within a network multiplexer are limited, for practical, technical, and economic reasons. Even in the case where a network multiplexer serves only to link multiple ethernets, an address table could potentially contain many trillions of entries. For this reason, and because network devices may be relocated from one network medium to another, it is technically impractical to hardwire an address table within a network multiplexer. Instead, the network multiplexer dynamically constructs an address table. In order to dynamically construct the address table, the network multiplexer requires a method for storing associations between discovered network addresses and ports quickly and economically within an address table of finite size so that the network multiplexer can quickly determine whether an incoming destination address occurs within the address table and, if so, determine the port associated with that destination address. Content addressable memories may be used for storing the address table. These are memories combined with a huge amount of hardware logic that allows memory locations to be addressed by the contents of the memory locations. However, content addressable memories are currently too expensive and too large for use in mass-produced network multiplexers. Alternatively, software or firmware routines, or logic circuits, that implement a hash table within random access memory (xe2x80x9cRAMxe2x80x9d) can provide functionality similar to content addressable memories. A discrete mathematical function is applied to an address to produce an index into a memory region in which the entry for that address is stored. However, because the discrete mathematical function maps a relatively large number of different possible addresses into a much smaller number of memory locations, collisions invariably occur between different addresses. Currently-available hash table implementations address the collision problem in order to attempt to maximize the capacity of a finite-sized address table, but characteristically do so at the expense of increased computational complexity and decreased computational efficiency. Network multiplexer designers, architects, and manufacturers have therefore recognized a need for an efficient and economical address table implementation that avoids the use of content addressable memories and avoids the complexity and inefficiency of currently-available hash table implementations.
The present invention provides a computationally and memory-efficient implementation of an address table for use in a network multiplexer. This implementation employs multiple hash functions as well as hash table reshuffling. However, the implementation is markedly more efficient and more computationally straightforward than currently-available implementations because hash table reshuffling is largely deferred to future address entry operations. The computational efficiency provided by the present invention is important in network multiplexers that store and forward hundreds or thousands of communications packets per second and the computational straightforwardness is necessary for designing integrated circuits that implement the address table in logic circuits.